'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-09-11 08:34:36
'''
'''
216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

tips:算是三个combination里面最简单的一个了，只用选择用或者不用就行了。代码如下：
不过存在更加简单更加节省空间的方法，直接在k个数里面搜索符合条件的，其他情况都不列举。
利用binary都属性，放在了binary中。
'''
import copy
from typing import List
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = []
        tmp = []
        def recurse(cur):
            if sum(tmp) == n and len(tmp) == k:
                ans.append(copy.copy(tmp))
                return

            if cur>=10:
                return
            if sum(tmp) >= n or len(tmp) >= k:
                return
            tmp.append(cur)
            recurse(cur+1)
            tmp.pop()
            recurse(cur+1)
        recurse(1)
        return ans
if __name__ == "__main__":
    solution = Solution()
    k = 3
    n = 9
    print(solution.combinationSum3(k, n))